0% completed
In this lesson, we’ll explore four different sorting algorithms:
- Bubble Sort
- Merge Sort
- Quick Sort
- Counting Sort.
We’ll provide code for each algorithm, followed by a detailed complexity analysis. Each algorithm will be evaluated based on its time and space complexity, helping you understand when to use each one.
1. Bubble Sort
Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Time Complexity for Bubble Sort
- Outer loop: The outer loop runs
Ntimes, whereNis the length of the input array. This contributes a time complexity offor the outer loop. - Inner loop (nested): For each iteration of the outer loop, the inner loop runs
N - i - 1times. In the first iteration, the inner loop runs approximatelyN - 1times, in the second iterationN - 2times, and so on. The total number of comparisons made can be expressed as:
This simplifies to
Overall time complexity:
Space Complexity for Bubble Sort
- The algorithm only uses a few variables (
i,j, and temporary variables for swapping), which require constant space. - No additional data structures are used that depend on the input size.
Overall space complexity:
2. Merge Sort
Merge Sort is a divide-and-conquer algorithm that splits the array into halves, recursively sorts each half, and then merges them back together in sorted order.
Time Complexity for Merge Sort
-
Divide Step:
- The
mergeSortfunction splits the array into two halves. - Time Complexity for Division:
for calculating midand slicing arrays. - This division step is performed at each recursive level, with each level having approximately
divisions for an input of size .
- The
-
Recursive Calls:
- The function recursively calls
mergeSorton both the left and right halves. - Number of Levels: The array is divided until each subarray has one element, resulting in approximately
levels of recursion.
- The function recursively calls
-
Merge Step:
- The merging process iterates over both halves and sorts them.
- Time Complexity for Merging:
at each level since all elements are processed once during merging. - Each level processes the entire array of size
N.
Overall Time Complexity:
- The merging process runs
at each level, and there are levels of recursion:
Space Complexity for Merge Sort
-
Auxiliary Space for Left and Right Halves:
- At each level of recursion, space is used for creating the left and right subarrays (
arr[:mid]andarr[mid:]). - This leads to
additional space for splitting arrays at each level of recursion.
- At each level of recursion, space is used for creating the left and right subarrays (
-
Recursive Call Stack:
- The depth of the recursion stack is
due to the binary splitting. - Each call adds a frame to the stack, but these do not contribute to more than
space.
- The depth of the recursion stack is
Overall Space Complexity:
- The merge process and auxiliary space for storing left and right halves contribute to
. - The recursive stack contributes
space.
Total Space Complexity:
3. Quick Sort
Quick Sort is a highly efficient sorting algorithm that picks a pivot and partitions the array into subarrays, sorting them recursively.
Time Complexity for Quick Sort
-
Partition Step:
- The array is partitioned into
left,middle, andrightsubarrays based on the pivot. - Time Complexity for Partitioning:
for each call as it requires iterating through the array to build the subarrays left,middle, andright.
- The array is partitioned into
-
Recursive Calls:
- The
quickSortfunction is recursively called onleftandrightsubarrays. - Best and Average Case:
- If the pivot splits the array into two roughly equal parts, each call processes
elements, leading to levels of recursion. - Total Time Complexity:
.
- If the pivot splits the array into two roughly equal parts, each call processes
- Worst Case:
- If the pivot is the smallest or largest element (e.g., already sorted or reverse-sorted arrays), one partition will have
elements, leading to levels of recursion. - Total Time Complexity in Worst Case:
.
- If the pivot is the smallest or largest element (e.g., already sorted or reverse-sorted arrays), one partition will have
- The
Overall Time Complexity:
- Best and Average Case:
. - Worst Case:
.
Space Complexity for Quick Sort
-
Auxiliary Space:
- The partitioning step creates new subarrays (
left,middle,right) at each level, requiring additional space proportional tofor each partition.
- The partitioning step creates new subarrays (
-
Recursive Call Stack:
- The depth of the recursion stack is
in the best and average cases, but can be in the worst case for highly unbalanced splits.
- The depth of the recursion stack is
Overall Space Complexity:
- Best and Average Case:
for the recursion stack. - Worst Case:
due to the maximum recursion depth.
Total Space Complexity:
- Auxiliary Space:
for subarrays created at each level.
4. Counting Sort
Counting Sort is a non-comparison-based sorting algorithm that counts the occurrences of each element and uses this count to place them in the correct position.
Time Complexity for Counting Sort
-
Finding the Maximum Element (
max(arr)):- Time Complexity:
– This step iterates through the array once to find the maximum value.
- Time Complexity:
-
Creating the Count Array:
- Time Complexity:
, where is the value of the maximum element in the array. This step initializes an array of size K + 1to zero.
- Time Complexity:
-
Counting the Occurrences:
- The
forloop that iterates througharrand increments the count in thecountarray runs in:- Time Complexity:
– It iterates through each element in the input array once.
- Time Complexity:
- The
-
Building the Sorted Array:
- The second
forloop iterates over thecountarray and extendssorted_arrbased on the counts. - Time Complexity:
– The loop runs times, and extending sorted_arrtakesacross all iterations.
- The second
Overall Time Complexity:
-
The total time complexity is:
This makes Counting Sort efficient when
(the range of input values) is not significantly larger than .
Space Complexity for Counting Sort
-
Count Array:
- The
countarray is created with a size of, where is the maximum element in arr. - Space Complexity:
– This space depends on the range of input values.
- The
-
Sorted Array:
- The
sorted_arris created to store the sorted output. - Space Complexity:
– It stores the sorted elements of the input array.
- The
Overall Space Complexity:
- The total space complexity is:
Which Sorting Algorithm is Better?
- Bubble Sort: Simple to implement but inefficient for large datasets (
). - Merge Sort: Reliable
performance but uses space. - Quick Sort: Efficient for most cases with
time, but worst case is . Uses less space ( ). - Counting Sort: Ideal for small ranges of integers;
time but uses more space ( ).
Best Overall Choice: Quick Sort for general cases due to its efficiency and average
On this page
- Bubble Sort
Time Complexity for Bubble Sort
Space Complexity for Bubble Sort
- Merge Sort
Time Complexity for Merge Sort
Space Complexity for Merge Sort
- Quick Sort
Time Complexity for Quick Sort
Space Complexity for Quick Sort
- Counting Sort
Time Complexity for Counting Sort
Space Complexity for Counting Sort
Which Sorting Algorithm is Better?